package cn.com.mdx.search;

/**
 * @author huangyuan
 * @date 2020/6/28
 * @description 二分查找
 */
public class BinarySearch {

    /**
     * 正序
     */
    private static final int AESC = 0;

    /**
     * 逆序
     */
    private static final int DESC = 1;

    /**
     * @param array    数组
     * @param value    查找的值
     * @param startPos 起始位置
     * @param endPos   结束位置
     * @param sortType 排序类型 0: 正序 1: 逆序
     * @return 查找的值位置
     * @methodName search
     * @Desc 全参数二分查找
     * @Author huangyuan
     * @Date 2020/6/28 5:32 下午
     */
    public static int binarySearch(int[] array, int value, int startPos, int endPos, int sortType) {
        if (startPos < 0 || startPos >= array.length) throw new IllegalArgumentException("起始位置超出范围");
        if (endPos < 0 || endPos >= array.length) throw new IllegalArgumentException("结束位置超出范围");
        int mid;
        if (AESC == sortType) {
            //正序
            while (startPos <= endPos) {
                mid = (startPos + endPos) >>> 1;
                if (value > array[mid]) startPos = mid + 1;
                else if (value < array[mid]) endPos = mid - 1;
                else return mid;
            }
        } else {
            //逆序
            while (startPos <= endPos) {
                mid = (startPos + endPos) >>> 1;
                if (value > array[mid]) endPos = mid - 1;
                else if (value < array[mid]) startPos = mid + 1;
                else return mid;
            }
        }
        return -1;
    }

    /**
     * @param array 数组
     * @param value 查找的值
     * @return 查找的值位置
     * @methodName binarySearch
     * @Desc 二分查找 - 正序
     * @Author huangyuan
     * @Date 2020/6/28 6:10 下午
     */
    public static int binarySearch(int[] array, int value) {
        if (array == null || array.length <= 0) throw new IllegalArgumentException("数组不能为空");
        return binarySearch(array, value, 0, array.length - 1, AESC);
    }

    /**
     * @param array 数组
     * @param value 查找的值
     * @return 查找的值位置
     * @methodName binarySearch
     * @Desc 二分查找 - 逆序
     * @Author huangyuan
     * @Date 2020/6/28 6:10 下午
     */
    public static int binarySearchDesc(int[] array, int value) {
        if (array == null || array.length <= 0) throw new IllegalArgumentException("数组不能为空");
        return binarySearch(array, value, 0, array.length - 1, DESC);
    }

    /**
     * @param array    数组
     * @param value    查找的值
     * @param startPos 起始位置
     * @param endPos   结束位置
     * @return 查找的值位置
     * @methodName search
     * @Desc 部分片段二分查找 - 正序
     * @Author huangyuan
     * @Date 2020/6/28 5:32 下午
     */
    public static int binarySearchFromPart(int[] array, int value, int startPos, int endPos) {
        return binarySearch(array, value, startPos, endPos, AESC);
    }

    /**
     * @param array    数组
     * @param value    查找的值
     * @param startPos 起始位置
     * @param endPos   结束位置
     * @return 查找的值位置
     * @methodName search
     * @Desc 部分片段二分查找 - 逆序
     * @Author huangyuan
     * @Date 2020/6/28 5:32 下午
     */
    public static int binarySearchFromPartDesc(int[] array, int value, int startPos, int endPos) {
        return binarySearch(array, value, startPos, endPos, DESC);
    }

    public static void main(String[] args) {
        int[] array = {1, 4, 6, 8, 11, 24, 67, 89, 100, 201, 302};
        int[] arrayDesc = {211, 120, 97, 87, 76, 53, 11, 8, 0, -1};
        System.out.println("正序4的位置:" + binarySearch(array, 4));
        System.out.println("正序5的位置:" + binarySearch(array, 5));
        System.out.println("逆序53的位置:" + binarySearchDesc(arrayDesc, 53));
        System.out.println("逆序11的位置:" + binarySearchDesc(arrayDesc, 111));
        System.out.println("部分正序6的位置:" + binarySearchFromPart(array, 6, 1, 3));
        System.out.println("部分正序100的位置:" + binarySearchFromPart(array, 100, 0, 5));
        System.out.println("部分逆序97的位置:" + binarySearchFromPartDesc(arrayDesc, 97, 2, 7));
        System.out.println("部分正序100的位置:" + binarySearchFromPartDesc(arrayDesc, 120, 2, 9));
    }
}

